package leetcode.editor.cn;

public class _215_KthLargestElementInAnArray {
    public static void main(String[] args) {
        Solution solution = new _215_KthLargestElementInAnArray().new Solution();
        int[] nums = {3, 2, 1, 5, 6, 4};
        int i = solution.findKthLargest(nums, 2);
        System.out.println(i);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        private void swap(int[] nums, int l, int r) {
            int temp = nums[l];
            nums[l] = nums[r];
            nums[r] = temp;
        }

        private int partition(int[] nums, int l, int r) {
            int pivot = nums[r];
            int pos = l;
            for (int j = l; j < r; j++) {
                if (nums[j] < pivot) {
                    swap(nums, j, pos);
                    pos++;
                }
            }
            swap(nums, pos, r);
            return pos;
        }

        public int findKthLargest(int[] nums, int k) {
            int n = nums.length;
            int l = 0, r = n - 1;
            int target = n - k;
            while (true) {
                int idx = partition(nums, l, r);
                if (idx == target) {
                    return nums[idx];
                } else if (idx < target) {
                    l = idx + 1;
                } else {
                    r = idx - 1;
                }
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}